#include <cstdio>
#include <vector>
#include <iostream>
#include <string>

using std::string;
using std::vector;

const string NONE="NONE";
const int MAX_LEN=100;

class BinaryCode{
public:
	vector<string> decode(string old);

private:
	int tryDecode(char* code,char* ret);
	void getV(vector<string>& v,char* code,char* ret,char* rett);
};

void BinaryCode::getV(vector<string>& v,char* ch,char* ret,char* rett){
	
	if(tryDecode(ch,ret)<0){
		v.push_back(NONE);
	}else{
		string s(rett);
		v.push_back(s);
	}
}

vector<string> BinaryCode::decode(string old){
	vector<string> v;
	vector<string> none;
	none.push_back(NONE);
	none.push_back(NONE);
		
	const char* chc=old.c_str();
	char* ch=strdup(chc);
	char* ret;
	
	if(*ch=='3'){
		return none;
	}else if(*ch=='2'){
		v.push_back(NONE);
		ret=(char*)malloc(MAX_LEN);
		ret[0]='1';
		ret[1]='1';
		getV(v,ch,ret,ret);
	}else if(*ch=='1'){
		//try 01 or 10
		ret=(char*)malloc(MAX_LEN);
		ret[0]='1';
		ret[1]='0';
		getV(v,ch,ret,ret);

		ret=(char*)malloc(MAX_LEN);		
		ret[0]='0';
		ret[1]='1';
		getV(v,ch,ret,ret);
	}else if(*ch=='0'){
		ret=(char*)malloc(MAX_LEN);		
		ret[0]='0';
		ret[1]='0';
		getV(v,ch,ret,ret);
		v.push_back(NONE);
	}
	return v;
}

int BinaryCode::tryDecode(char* ch,char* ret){
	std::cout<<"try decode :"<<string(ch)<<","<<string(ret)<<"\n";
	ret++;
	char *h;
	for(h=ch+1;*h!='\0';h++){
		//std::cout<<"check "<<*h<<"\n";
		if(*h=='3'){
			if(*ret!='1' || *(ret-1)!='1'){
				return -1;
			}else{
				*(++ret)='1';
			}		
		}else if(*h=='2'){
			if(*ret=='1' && *(ret-1)=='1')
				*(++ret)='0';
			else if(*ret=='0' && *ret=='0')
				return -1;
			else
				*(++ret)='1';
		}else if(*h=='1'){
			if(*ret=='1' || *(ret-1)=='1')
				*(++ret)='0';
			else
				*(++ret)='1';
		}else if(*h=='0'){
			*(++ret)='0';
		}
	}
	//test final data
	h--;
	ret--;
	switch(*h){
		case '3':
			if(*ret=='1')
		break;
		case '2':
		break;
		case '1':
		break;
		case '0':
		break;
	}
	//*(++ret)='\0';
	*ret='\0';
	
	return 0;
}

int main(){
	BinaryCode bc;
	//string code="22111";
	string codes[]={"22111","123210120","3","123210122"};
	//string code="123210120";
	for(int i=0;i<4;i++){
		string code=codes[i];
		vector<string> v=bc.decode(code);
		std::cout<<"decode: "<<code<<"\n";

		vector<string>::const_iterator it=v.begin();
		for(;it!=v.end();it++){
			std::cout<<*it<<"  ";
		}
		std::cout<<"\n";
	}
	
	return 0;
}